package com.peng.leetcode.jump;

import java.util.HashSet;
import java.util.Set;

/**
 * CanReach
 * 这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。
 * <p>
 * 请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处
 *
 * @author: lupeng6
 * @create: 2020/11/28 21:16
 */
public class CanReach {

    public static void main(String[] args) {
        int[] arr = {4,2,3,0,3,1,2};
        int start = 0;
//        int[] arr = {3, 0, 2, 1, 2};
//        int start = 2;
        System.out.println(new Solution().canReach(arr, start));
    }

    static class Solution {
        public boolean canReach(int[] arr, int start) {
            return dfs(arr, start, new HashSet<>());
        }

        private boolean dfs(int[] arr, int start, Set<Integer> path) {
            if (arr[start] == 0) {
                return true;
            }

            boolean flag1 = false;
            boolean flag2 = false;
            int lIndex = start + arr[start];
            int rIndex = start - arr[start];

            path.add(start);

            if (lIndex >=0 && lIndex < arr.length && !path.contains(lIndex)) {
                flag1 = dfs(arr, lIndex, path);
                path.remove(start);
            }
            if (rIndex >=0 && rIndex < arr.length && !path.contains(rIndex)) {
                flag2 = dfs(arr, rIndex, path);
                path.remove(start);
            }

            return flag1 || flag2;
        }
    }
}
